package ppd;

import java.util.Arrays;
import java.util.List;

/**
 * <p>
 *      快排
 *      [3,2,3,1,2,4,5,5,6]
 * </p>
 *
 * @author weiyunbing
 * @since 2025/6/23 20:38
 **/
public class FastSort {



        // 主方法：对外暴露的排序接口
        public static void quickSort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return; // 边界条件检查
            }
            sort(arr, 0, arr.length - 1); // 调用核心排序逻辑
        }

        // 核心递归排序方法
        private static void sort(int[] arr, int left, int right) {
            if (left >= right) {
                return; // 递归终止条件
            }
            int pivotIndex = partition(arr, left, right); // 获取分区点
            sort(arr, left, pivotIndex - 1);  // 递归排序左子数组
            sort(arr, pivotIndex + 1, right); // 递归排序右子数组
        }

        // 分区操作（关键步骤）
        private static int partition(int[] arr, int left, int right) {
            int pivot = arr[left]; // 基准值（通常选第一个元素）
            int i = left, j = right;

            while (i < j) {
                // 从右向左找第一个小于pivot的值
                while (i < j && arr[j] >= pivot) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j]; // 将小值移到左侧
                }

                // 从左向右找第一个大于pivot的值
                while (i < j && arr[i] <= pivot) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i]; // 将大值移到右侧
                }
            }
            arr[i] = pivot; // 将基准值放到正确位置
            return i; // 返回分区点索引
        }

        // 测试用例
        public static void main(String[] args) {
            int[] arr = {6, 2, 8, 5, 1, 9, 3, 7};
            quickSort(arr);
            System.out.println(Arrays.toString(arr));
        }
}
